/* eslint-disable no-console */
/* eslint-disable no-param-reassign */
import { exchange, randomInt } from './common'

/**
 * 使用数组区间中最后一个元素作为标准值，把数组分成前后两个部分。
 * 第一个部分包含所有小于等于标准值的元素。
 * 第二个部分包含所有大于标准值的元素。
 * 返回第一个部分最后一个元素的索引，也就是标准值最后的位置。
 * @param A the array
 * @param first the section first index
 * @param last the section last index
 * @returns the position of the standard value which is the last value of the input array
 */
function partition(A: number[], first: number, last: number): number {
	const lastValue = A[last]
	let i = first - 1

	// 把区间中（包括最后一个）小于等于最后一个值的元素，前移到头部
	for (let j = first; j < last; j += 1) {
		if (A[j] <= lastValue) {
			i += 1
			exchange(A, i, j)
		}
	}
	// 前移最后一个元素
	exchange(A, i + 1, last)

	// 返回大于最后一个值的索引
	return i + 1
}

function randomizedPartition(A: number[], first: number, last: number): number {
	const i = randomInt(first, last)
	exchange(A, last, i)
	return partition(A, first, last)
}

/**
 * 求数组的顺序值
 * @param A 数组 
 * @param first the first index
 * @param last the last index
 * @param rankIndex 1-based rank index
 */
export function randomizedSelect(A: number[], first: number, last: number, rankIndex: number): number {
	if (first === last) {
		return A[first]
	}

	const q: number = randomizedPartition(A, first, last)
	const k = q - first + 1
	if (rankIndex === k) {
		return A[q]
	}
	if (rankIndex < k) {
		return randomizedSelect(A, first, q - 1, rankIndex)
	}

	return randomizedSelect(A, q + 1, last, rankIndex - k + 1)
}

console.log(randomizedSelect([7, 6, 5, 4, 3, 2, 1], 0, 6, 4))
